package com.xj.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 把二叉搜索树转换为累加树
 */
public class L538_把二叉搜索树转换为累加树 {

    /**
     * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     *
     *  
     *
     * 例如：
     *
     * 输入: 原始二叉搜索树:
     *               5
     *             /   \
     *            2     13
     *
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     *  
     *
     * 注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
     */
    public static void main(String[] args) {
        TreeNode root=new TreeNode(5);
        root.left=new TreeNode(2);
        root.right=new TreeNode(13);

        TreeNode node=convertBST(root);
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            System.out.println(tmp.val);
            if(tmp.left!=null){
                queue.add(tmp.left);
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
            }
        }

        TreeNode root2=new TreeNode(2);
        root2.left=new TreeNode(1);
        root2.right=new TreeNode(3);

        TreeNode node2=convertBST(root2);
        Queue<TreeNode> queue2=new ArrayDeque<>();
        queue2.add(node2);
        while (!queue2.isEmpty()){
            TreeNode tmp2=queue2.poll();
            System.out.println(tmp2.val);
            if(tmp2.left!=null){
                queue2.add(tmp2.left);
            }
            if(tmp2.right!=null){
                queue2.add(tmp2.right);
            }
        }
    }

    //自己的解法：右中左的遍历方式，逐个累加。全局变量注意最后清空
    static int count=0;
    public static TreeNode convertBST(TreeNode root) {
        TreeNode node=root;
        reverseInorder(node);
        count=0;
        return root;
    }

    public static void reverseInorder(TreeNode root) {
        if(root==null){
            return ;
        }
        reverseInorder(root.right);
        root.val=root.val+count;
        count=root.val;
        reverseInorder(root.left);
    }

    //官方解法：精简的递归
    static private int sum = 0;
    public static TreeNode convertBSTOffice(TreeNode root) {
        if (root != null) {
            convertBSTOffice(root.right);
            sum += root.val;
            root.val = sum;
            convertBSTOffice(root.left);
        }
        return root;
    }
}
